package interview_59_1

type MyQueue struct {
	items []int
}

func (q MyQueue) Length() int {
	return len(q.items)
}

func (q MyQueue) isEmpty() bool {
	if len(q.items) != 0 {
		return false
	}
	return true
}

func (q *MyQueue) RPush(n int) bool {
	q.items = append(q.items, n)
	return true
}

func (q *MyQueue) RPushCheck(idx, n int, nums []int) bool {

	b := true
	if q.isEmpty() {
		b = false
	}

	for b {
		re, ok := q.RTop()
		if ok {
			if n > nums[re] {
				q.RPop()
			} else {
				b = false
			}
		} else {
			b = false
		}
	}

	q.items = append(q.items, idx)
	return true
}

func (q *MyQueue) LPop() (int, bool) {
	if q.isEmpty() {
		return 0, false
	}
	el := q.items[0]
	q.items = q.items[1:]
	return el, true
}

func (q MyQueue) LTop() (int, bool) {
	if q.isEmpty() {
		return 0, false
	}
	el := q.items[0]
	return el, true
}

func (q *MyQueue) RPop() (int, bool) {
	if q.isEmpty() {
		return 0, false
	}
	el := q.items[len(q.items)-1]
	q.items = q.items[:len(q.items)-1]
	return el, true
}

func (q *MyQueue) RTop() (int, bool) {
	if q.isEmpty() {
		return 0, false
	}
	el := q.items[len(q.items)-1]
	return el, true
}

func (q *MyQueue) Clear() bool {
	q.items = q.items[0:0]
	return true
}

func NewMyQueue() *MyQueue {
	return &MyQueue{}
}

func maxSlidingWindow2(nums []int, k int) []int {

	//[10 9 8] 7 6 5 4 3 2 1
	//10 [9 8 7] 6 5 4 3 2 1
	//10 9 [8 7 6] 5 4 3 2 1
	//10 9 8 [7 6 5] 4 3 2 1
	//10 9 8 7 [6 5 4] 3 2 1
	//10 9 8 7 6 [5 4 3] 2 1
	//10 9 8 7 6 5 [4 3 2] 1
	//10 9 8 7 6 5 4 [3 2 1]

	q := NewMyQueue()
	maxs := NewMyQueue()
	var res []int

	length := len(nums)

	for i := 0; i < length; i++ {

		val := nums[i]

		if first, ok := maxs.LTop(); ok {
			//fmt.Println(first, i, i-k)
			if first == i-k {
				maxs.LPop()
			}
		}

		if first, ok := maxs.LTop(); ok {
			if val >= nums[first] {
				maxs.Clear()
			}
		}
		// 每次push进去的时候往前遍历
		maxs.RPushCheck(i, val, nums)

		q.RPush(val)

		if q.Length() == k {
			if first, ok := maxs.LTop(); ok {
				res = append(res, nums[first])
			}
			q.LPop()
		}
	}

	return res
}
